package algorithm.tree;

import algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode
 * 199. Binary Tree Right Side View
 *
 * https://leetcode.com/problems/binary-tree-right-side-view/
 * Difficulty : Medium
 * Topic: Tree, DFS, BFS
 *
 * 打印一棵树的右视图
 *
 * Created by yzy on 2020-03-31 16:50
 */
public class RightSideView {


    /**
     * 广度优先(BFS)的思路
     * 右视图，就是从右边看，第一个看到的元素。
     * 所以，使用BFS，取每一层的最右边元素放到result里就可以了，很简单。
     * @param root
     * @return
     */
    public List<Integer> rightSideView_BFSWay(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        List<TreeNode> currLevelNodes = new ArrayList<>();
        currLevelNodes.add(root);
        BFS(result, currLevelNodes);
        return result;
    }

    /**
     * Runtime: 1ms, faster than 75.16%
     * Memory: 38.4MB, less than 5.88%
     * @param result
     * @param currLevelNodes
     */
    private static void BFS(List<Integer> result, List<TreeNode> currLevelNodes){
        if(currLevelNodes==null || currLevelNodes.size() == 0){
            return;
        }
        int rightVal = currLevelNodes.get(currLevelNodes.size()-1).val;
        result.add(rightVal);
        List<TreeNode> nextLevelNodes = new ArrayList<>();
        for(TreeNode node : currLevelNodes){
            if(node.left != null){
                nextLevelNodes.add(node.left);
            }
            if(node.right != null){
                nextLevelNodes.add(node.right);
            }
        }
        BFS(result, nextLevelNodes);
    }


    /**
     * 深度优先(BFS)的思路
     * 1、每一层，只选一个最靠右的元素放入结果集中.(那么最右边的优先加入结果集，同一层的递归就不会再往里加元素了)
     * 2、层数 == 结果集的大小
     * @param root
     * @return
     */
    public List<Integer> rightSideView_DFSWay(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        DFS(root, result, 0);
        return result;
    }


    /**
     * Runtime: 0ms faster than 100.0%
     * Memory: 38.4MB, less than 5.88%
     * @param curr
     * @param result
     * @param depth
     */
    private static void DFS(TreeNode curr, List<Integer> result, int depth){
        if(curr == null){
            return;
        }
        // 如果层数==结果集大小，那么说明当前层还没有元素加进结果集，可以加进去
        if(result.size() == depth){
            result.add(curr.val);
        }

        // 排个优先级，先右再左，可以保证同一层最右边的加入结果集
        DFS(curr.right, result, depth+1);
        DFS(curr.left, result, depth+1);
    }
}
